package structure.array;


import com.sun.xml.internal.messaging.saaj.soap.impl.HeaderImpl;

import java.util.HashSet;
import java.util.Set;

/**
 * 地址：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/
 * <p>
 * 题目：剑指 Offer 11. 旋转数组的最小数字
 * <p>
 * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。
 * 例如，数组[3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
 * <p>
 * 示例 1：
 * <p>
 * 输入：[3,4,5,1,2]
 * 输出：1
 * 示例 2：
 * <p>
 * 输入：[2,2,2,0,1]
 * 输出：0
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Leetcode_Sword_Offer_11 {
    public static void main(String[] args) {

        int[] input = new int[]{3,4,5,1,2};
        int[] input1 = new int[]{2,2,2,0,1};

        System.out.println(minArray(input));
        System.out.println(minArray(input1));


    }

    /**
     * 解法2：
     * 思路： 根据值去找下标。
     * <p>
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * <p>
     * 考虑边界条件：
     * 1、数组为空
     * <p>
     * <p>
     * 执行结果：通过
     * 执行用时：1 ms, 在所有 Java 提交中击败了 83.76% 的用户
     * 内存消耗：46.3 MB, 在所有 Java 提交中击败了 51.08% 的用户
     * <p>
     * <p>
     *
     * @return
     */
    public static int minArray(int[] numbers) {
        int low = 0;
        int high = numbers.length-1;
        while (low < high){
            int pivot = low + (high - low)/2;
            if(numbers[pivot] < numbers[high]){
                high = pivot;
            }else if(numbers[pivot] > numbers[high]){
                low = pivot +1;
            }else{
                high -= 1;
            }
        }
        return numbers[low];
    }


    /**
     * 解法1：
     * 思路： 默认第一个是最小值，依次往后面找，直到找到第一个比它小的数字
     * <p>
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * <p>
     * 执行结果：通过
     执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     内存消耗：38.2 MB, 在所有 Java 提交中击败了59.57%的用户
     * <p>
     * 可以优化的地方在哪里？
     * 利用递增的特性，可以使用二分查找法，可以降低时间复杂度至 O(logN)
     *
     * @return
     */
    public static int minArray1(int[] numbers) {
        int min = numbers[0];
        for (int i = 1; i < numbers.length; i++) {
            if(numbers[i] < min){
                return numbers[i];
            }
        }
        return min;
    }
}
